1. Field of the Invention
The present invention relates to a Bose-ChaudhuriHocquenghem code (referred to as a BCH code hereinafter) decoder and a method for decoding a BCH code, and more particularly, to a BCH code decoder for correcting a natural number N or less of error bits occurring in a code sequence composed of bits encoded by a BCH encoding method, and a method for decoding a BCH code so as to correct a natural number N or less of error bits occurring in a code sequence composed of bits encoded by a BCH encoding method.
2. Description of the Related Art
Conventionally, in order to correct one or more bit errors occurring in digital data upon transmitting the digital data, a method has been used such that digital data composed of an information sequence to which a check sequence is added on a transmission side are transmitted, and bit errors occurring in digital data upon transmitting them are corrected by a error correction unit on a reception side. As one of error correction codes for obtaining the above-mentioned check sequence, the BCH code has been used.
FIG. 1 shows a conventional BCH code decoder which is well known to those in the art (For example, see Toshihide HABUTSU, "Error correction by the BCH code", Hohsoh gijutsu, November 1983, pp 1111). The composition of the conventional BCH decoder will be described below with reference to FIG. 1.
Referring to FIG. 1, a code sequence composed of an information sequence and a check sequence which is coded by the BCH code is inputted in a serial form through an input terminal 111 to a syndrome generator 101 and a delay circuit 108. The syndrome generator 101 generates a syndrome based on a check matrix of the BCH code from the code sequence inputted through the input terminal 111, and outputs the generated syndrome to a syndrome memory 102. The syndrome memory 102 temporarily stores the generated syndrome at a timing when the generation of the syndrome performed by the syndrome generator 101 has been completed, and outputs the stored syndrome to a code converter 103.
The code converter 103 of a read only memory (referred to as a ROM hereinafter) converts the syndrome inputted from the syndrome memory 102 into signals for representing different error bit positions of one or two bit errors to coincidence judgment circuits 105 and 106, respectively. Data of bit error positions corresponding to all the syndromes previously obtained in respective error patterns with respect to all the bit errors of two bits or less are stored at the addresses which are respectively the same as the above syndromes in the ROM of the code converter 103. When the syndrome temporarily stored in the syndrome memory 102 is inputted to an address terminal of the ROM of the code converter 103, data of the bit error positions corresponding to the inputted syndrome are outputted from a data terminal thereof.
The delay circuit 108 delays the code sequence inputted through the input terminal 111 by a predetermined delay time, and sequentially outputs them to a first input terminal of an exclusive OR gate 109, which is provided for inverting a bit inputted from the delay circuit 108 only when the inputted bit is an error bit. A counter 107 generates a signal representing a bit position of the delayed code sequence which is outputted from the delay circuit 108 in synchronization with the delayed code sequence by counting a clock of the code sequence, and outputs the generated signal to both coincidence judgment circuits 105 and 106.
The coincidence judgment circuit 105 compares the error bit position outputted from the code converter 103 with the signal for representing the bit position of the code sequence which is outputted from the counter 107. Then, when the error bit position coincides with the bit position of the code sequence, the coincidence judgment circuit 105 outputs an error correction signal having a high level to a first input terminal of an OR gate 110. On the other hand, when the error bit position does not coincide with the bit position of the code sequence, the coincidence judgment circuit 105 outputs the error correction signal having a low level to the first input terminal of the OR gate 110.
The coincidence judgment circuit 106 generates an error correction signal by comparing the error bit position outputted from the code converter 103 with the signal representing the bit position of the code sequence which is outputted from the counter 107 in a manner similar to that of the coincidence judgment circuit 105, and then, outputs the generated error correction signal to the second input terminal of the OR gate 110.
The OR gate 110 calculates the logical sum of the error correction signal inputted from the coincidence judgment circuit 105 and the error correction signal inputted from the coincidence judgment circuit 106, and outputs a signal of the logical sum to the second input terminal of the exclusive OR gate 109. The exclusive OR gate 109 calculates the exclusive logical sum of the signals inputted from the delay circuit 108 and the OR gate 110, namely inverts a bit inputted from the delay circuit 108 only when the inputted bit is an error bit, and outputs the signal of the exclusive logical sum to an output terminal 112.
The action of the conventional BCH decoder shown in FIG. 1 is described below.
When a transmitted code sequence is inputted in a serial form through the input terminal 111, a syndrome is generated from the inputted code sequence by the syndrome generator 101, and then, the generated syndrome is temporarily stored in the syndrome memory 102. Thereafter, the syndrome stored in the syndrome memory 102 is converted into signals of the error bit positions of the error bits occurring in the code sequence by the code converter 103. Simultaneously, the code sequence is inputted to the delay circuit 108, and then, the delay circuit 108 delays the inputted code sequence by the predetermined delay time and outputs the delayed code sequence to the exclusive OR gate 109. At that time, the counter 107 is started, and then, the counter 107 generates a signal representing a bit position of the delayed code sequence which is outputted from the delay circuit 108 in synchronization with the delayed code sequence by counting a clock of the code sequence, and outputs the signal to both coincidence judgment circuits 105 and 106.
The coincidence judgment circuits 105 and 106 respectively compare the different error bit positions outputted from the code converter 103 with the bit position of the code sequence represented by the signal which is generated by the counter 107. When either one of the coincidence judgment circuits 105 and 106 judges that the error bit position outputted from the code converter 103 coincides with the bit position of the code sequence represented by the above-mentioned signal, an error correction signal having an high level is outputted from the OR gate 110 to the exclusive OR gate 109. The exclusive OR gate 109 inverts the bit of the code sequence outputted from the delay circuit 108 if the error correction signal becomes a high level. Therefore, one or two error bits included the code sequence are corrected, and then, the code sequence composed of only the correct bits when the number of the error bits is two or less is outputted as the decoded code sequence from the exclusive OR gate 109 to the output terminal 112.
However, in the BCH decoder constructed as described above, it is necessary for the ROM of the code converter 103 to have the addresses of a bit number which is the same as the number of all of syndrome, and it is also necessary for data of a bit number representing all the error bit positions to be stored at these addresses in the ROM of the code converter 103. Therefore, the memory capacity of the ROM of the code converter 103 becomes extremely large, and then, there is a problem in that the circuit size of the BCH decoder is enlarged.
Further, as the code length of the code used for the error correction becomes longer, the necessary memory capacity of the ROM of the code converter 103 exponentialfunctionally increases depending on the code length, and then, the circuit size of the decoder is extremely enlarged, resulting in difficulty of realizing the decoder.
For example, in the case of a BCH (15, 7) code having a code length of 15 bits and a length of a information code of 7 bits, the bit number of the syndrome is eight, and the number of the addresses of the ROM is eight. Further, it is necessary to store data of eight bits at one address of the ROM in order to represent information of two positions in the code having a code length of 15. As a result, it is necessary to provide a ROM having a memory capacity of 2048 (=8.times.2.sup.8) bits.
Furthermore, in the case of a BCH (255, 239) code, it is necessary to provide a ROM having a memory capacity of 1048576 bits.
Since it is necessary to provide storage means such as a ROM, there is such a problem that it is difficult to construct the entire BCH decoder using an LSI chip.